﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

/*
杨辉三角形，又称帕斯卡三角形、贾宪三角形、海亚姆三角形，它的排列形如三角形。

因为首现于南宋杨辉的《详解九章算法》得名，而书中杨辉说明是引自贾宪的《释锁算书》，故又名贾宪三角形。

古代波斯数学家欧玛尔·海亚姆也描述过这个三角形。在欧洲，因为法国数学家布莱兹‧帕斯卡在1653年的《论算术三角》中首次完整论述了这个三角形，故也被称作帕斯卡三角(Pascal’s triangle)。


在最上面一行的中央写下数字 1；

第二行，写下两个1，和上一行形成三角形；

随后的每一行，开头和最后的数字都是1，其他的每个数都是它左上方和右上方的数之和，就是说除每行最左侧与最右侧的数字以外，每个数字等于它的左上方与右上方两个数字之和。

*/

//1、定义一个9行9列的二维整型数组；
//2、数组所有元素都赋值为1；
//3、输出数组所有元素

/*
中间位置的数字是由它上一行对应位置的数字以及上一行对应位置左侧的数字相加得到；

因为下一行的情况总需要由上一行的情况推出，即我们需要记录每一行的结果。

所以构建杨辉三角本质上是一个动态规划问题，我们可以总结出如下推导式：

dp[i][j] = dp[i − 1][j − 1] + dp[i − 1][j]dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]dp[i][j]=dp[i−1][j−1]+dp[i−1][j]

*/

//注意点
/*
1、每行前输出不等的空格；

2、为何i / 2？因为：居中只需左边加空格；

3、为何要乘6？因为：输出时用%6d；

4、为何要用26减？因为：不大不小刚刚好
*/
int main()
{
    //定义一个9行9列的二维整型数组
    int data[9][9];

    int i = 0;
    int j = 0;

    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            //数组所有元素都赋值为1
            data[i][j] = 1;
        }
    }

    //dp
    for (i = 1; i < 9; i++)
    {
        for (j = 1; j < i; j++)
        {
            data[i][j] = data[i - 1][j] + data[i - 1][j - 1];
        }
    }

    //输出数组所有元素
    for (i = 0; i < 9; i++)
    {
        //用三角形的方式打印
        for (int k = 0; k < 26 - (6 * i / 2); k++)
        {
            printf(" ");
        }

        for (j = 0; j <= i; j++)
        {
            printf("%6d", data[i][j]);
        }
        printf("\n");
    }
    return 0;
}
